package com.xhj.joffer.array;

import org.junit.Test;

import java.util.Arrays;
/** @author haijianxia pure_xhj@163.com @Date 2021-09-14 @Time 17:55 */
public class MergeArrays {
  public static void main(String[] args) {
    int[] array1={1,3,5,7};
    int[] array2={2,4,8,12,34,50,90};
    int[] merge=testMerge(array1,array2);
    System.out.println("result: "+Arrays.toString(merge));

	  System.out.println("==========================result.fori==========================");
	  int[] ints = test2(array1, array2);
	  System.out.println("ints: "+Arrays.toString(ints));

  }
  /** 合并两个有序数组 */
  @Test
  public static int[] testMerge(int[] array1, int[] array2) {
    System.out.println("=============testMerge==============");
    System.out.println("合并两个有序数组");
    long timeMerge = System.currentTimeMillis();
    /**
     * 默认非减数组
     * 思路一: 双数组遍历, 挨个看
     * 思路二: 遍历result
     */
    int index1 = 0, index2 = 0, indexR = 0; // - - - - - - -指针指向当前位置
    boolean makeOuterBreak = false;
    boolean makeInnerBreak = false;
    int[] result = new int[array1.length + array2.length];
    for (int i = 0; i <= array1.length; i++) {
      for (int j = index2; j < array2.length; j++) {
        if (indexR == result.length) {
          makeOuterBreak = true;
		      makeInnerBreak = true;
        }
	      if (makeInnerBreak == true) { makeInnerBreak = false; break; }
        if (i == array1.length) {

        }else{
          if (array1[index1] < array2[index2]) {
            result[indexR++] = array1[index1];
            index1=i+1;
          }else {
            result[indexR++] = array2[index2];
            index2=j+1;
          }
        }
      }
	    if (makeOuterBreak == true) { makeOuterBreak = false;break; }
    }

    long timeMergeMerge = System.currentTimeMillis() - timeMerge;
    System.out.println("\ntestMerge 耗时 =  " + timeMergeMerge + "ms");
    System.out.println("=================================");

    return result;
  }

  /** 思路二: 遍历result */
  @Test
  public static int[] test2(int[] a1, int[] a2) {
  	System.out.println("\n=============test2==============");
  	System.out.println("思路二: 遍历result");
  	long time2 = System.currentTimeMillis();

  	int[] result = new int[a1.length+a2.length];
  	int index1=0, index2=0;
  	int min=0;
	  // 比较两个数组的两个当前索引位置的元素的大小
	  // 取到一个最小的
	  // 取到数的数组的当前指针+1
	  // 当一个数组的索引到达数组末尾时, 终止比较
	  // 直接将另一数组的剩余元素转给result
	  // over
	  // to(n) so(1)

    // 遍历result[]
    for (int i = 0; i < result.length; i++) {
	    // 有数组已经被用完
      if (index1==a1.length || index2==a2.length){
        if (index1 == a1.length && index2!=a2.length) {
	        min=a2[index2++];
        }else if (index1 != a1.length && index2==a2.length) {
	        min=a1[index1++];
	      }else{

	      }
      }
      // 两个数组都还有元素
      else{
        if (a1[index1]<a2[index2]) {
	        min=a1[index1++];
        }else{
	        min=a2[index2++];
        }
      }
      result[i]=min;
    }

  	long time22  = System.currentTimeMillis() - time2;
  	System.out.println("test2 耗时 =  " + time22  + "ms");
  	System.out.println("=================================");

  	return result;
  }

}
